package array

func findKthLargest(nums []int, k int) int {

	return quickSort(nums, 0, len(nums)-1, k)
}

func quickSort(nums []int, left int, right int, k int) int {

	if left > right {
		return -1
	}

	i, j := left, right
	base := nums[left]
	for i < j {
		for i < j && base <= nums[j] {
			j--
		}
		for i < j && nums[i] <= base {
			i++
		}

		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}

	nums[left], nums[i] = nums[i], nums[left]

	if i == len(nums)-k {
		return nums[i]
	} else if i < len(nums)-k {
		return quickSort(nums, i+1, right, k)
	} else {
		return quickSort(nums, left, i-1, k)
	}

}
